package leetcode每日一题;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 分发糖果 {
    public static void main(String[] args) {

    }


    public static int candy2(int[] ratings) {

        return -1;
    }


    public static int candy3(int[] ratings) {
        int len = ratings.length;
        if(len == 0) {return 0;}
        if(len == 1) {return 1;}
        // [1,2,3,2]
        int count = (ratings[0] <= ratings[1]) ? 1 : 2; // 初始化，该属性记录最少的糖果数
        for(int i = 1; i < len; i++) {
            // 如何判断当前孩子能分到的最少的糖果呢?
            /*
                判断当前孩子的左边开始比它小的连续的以当前孩子为末尾的孩子数
                判断当前孩子的右边开始比它小的连续的以当前孩子为起点的孩子数
                然后选取之间最大的一个作为糖果数
            */
            if(i == len-1) {
                // 最后一个孩子单独判断
                int temp = i;
                int cur = 0;
                while(ratings[temp] > ratings[temp-1]) {
                    cur++;
                    temp--;
                    if(temp == 0) {
                        break;
                    }
                }
                if(cur == 0) {
                    count++;
                } else {
                    // 4 3 2 2 1 1
                    // 3 2 1 2 1 1
                    count += (cur+1);
                }
            } else {
                // 定义两个指针
                int temp1 = i; // 左移动指针
                int temp2 = i; // 右移动指针
                int cur1 = 0; // 记录左边比当前孩子的小的
                int cur2 = 0; // 记录右边比当前孩子小的
                while(ratings[temp1-1] < ratings[temp1]) {
                    cur1++;
                    temp1--;
                    if(temp1 == 0) {
                        break;
                    }
                }
                while(ratings[temp2+1] < ratings[temp2]) {
                    cur2++;
                    temp2++;
                    if(temp2 == len-1) {
                        break;
                    }
                }
                if(cur1 == 0 && cur2 == 0) {
                    count++;
                } else {
                    count += Math.max(cur1+1,cur2+1);
                }
            }
        }
        return count;
    }
}
